package com.gxc.recursion;

/**
 *小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装包装不可拆分。
 * 可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。
 * 如果不能购买恰好n个苹果，小虎将不会购买。
 * 输入一个整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。
 * 如果无论如何都不能正好装下，返回-1。
 */
public class MinimumBag {

    public static void main(String[] args) {
        int n = 60;
        int minBag = getMinBag(n);
        System.out.println(minBag);
        System.out.println("----------");
        //总结规律
        for (int i = 0; i < 100; i++) {
            if (getMinBag(n) != sumUp(n)) {
                System.out.println("结果不一致");
            }
        }
    }


    private static int getMinBag(int n) {
        //24  6和8的最小公约数是24 所以超过24的值都可简化为24内的值
        int simple = n/24;
        n = n - simple *24;
        //先按照8 的最大数量计算，不满足则逐渐减一个8袋子的数量，增加6袋子的数量，看是否满足
        int remaining = 0;
        int eightNum = n/8;
        for (int num = eightNum; num >= 0; num--) {
            remaining = n - num * 8;
            if (remaining % 6 == 0) {
                return num + remaining/6 + simple * 3;
            }
        }
        return -1;
    }

    private static int sumUp(int n) {
        //奇数不可能匹配
        if ((n & 1) != 0) return -1;
        if (n < 18) {
            return n==0?0:
                    (n==6 || n==8?1:
                            (n==12||n==14||n==16?
                                    2:-1));
        }
        return (n-18)/8+3;
    }
}
